package tasks.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * leetcode239
 */
public class SlidingMxValueJava {
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums == null || nums.length == 0 || k <= 0) {
                return new int[0];
            }

            // 双端队列用于存储索引
            Deque<Integer> deque = new ArrayDeque<>();
            List<Integer> result = new ArrayList<>();

            for (int i = 0; i < nums.length; i++) {
                // 移除不在当前窗口的元素
                if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                    deque.pollFirst();
                }

                // 保持双端队列中的元素是递减的
                while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                    deque.pollLast();
                }

                // 将当前元素的索引添加到双端队列中
                deque.offerLast(i);

                // 当前窗口已经形成，可以开始记录结果
                if (i >= k - 1) {
                    result.add(nums[deque.peekFirst()]);
                }
            }

            // 将结果列表转换为数组
            int[] resultArray = new int[result.size()];
            for (int i = 0; i < result.size(); i++) {
                resultArray[i] = result.get(i);
            }

            return resultArray;
        }

    }
}
